/*
 * @lc app=leetcode.cn id=2965 lang=cpp
 *
 * [2965] 找出缺失和重复的数字
 */
#include <vector>
using namespace std;
// @lc code=start
class Solution {
public:
    vector<int> findMissingAndRepeatedValues(vector<vector<int>>& grid) {
        int lost=0;
        int repeat=0;
        int n=grid.size();
        int aim=1;
        for (int i =0;i<n;i++){
            for(int j =0;j<n;j++){
                while(aim!=grid[i][j]){
                    if (!this->swap(grid,i,j)){
                        lost=grid[i][j];
                        repeat=aim;
                        break;
                    }
                }
                ++aim;
            }
        }
        auto res=vector<int>(2);
        res[0]=(lost);
        res[1]=repeat;
        return res;
    }
    bool swap(vector<vector<int>> &grid ,int x1,int y1){
        int tem =grid[x1][y1];
        int x2=tem/grid.size();
        int y2=tem%grid.size();
        if (y2==0){
            y2=grid.size()-1;
            x2--;
        }else{
            y2--;
        }
        if (grid[x1][y1]==grid[x2][y2]){
            return false;
        }
        tem=grid[x2][y2];
        grid[x2][y2]=grid[x1][y1];
        grid[x1][y1]=tem;
        return true;
    }
    
};


// @lc code=end